def dijkstra(Adj,s):
    V = xrange(len(Adj))
    d = [maxint] * len(V)
    pi = [None] * len(V)
    done = ['no'] * len(V)
    d[s] = 0
    Q = []
    heappush(Q, (d[s], 0))
    while len(Q)>0:
        _, u = heappop(Q)
        if done[u] == 'yes': continue
        done[u] = 'yes'
        for (v, w) in Adj[u]:
            if done[v] == 'no':
                if d[v] > d[u] + w:
                    d[v] = d[u] + w
                    pi[v] = u
                    heappush(Q, (d[v], v));
    return pi, d

if __name__=='__main__':
    from heapq import heappush, heappop
    from sys import maxint
    from pprint import pprint
    Adj = [[(1,10),(2,5)],[(2,2),(3,1)],[(1,3),(3,9),(4,2)],[(4,4)],[(3,6),(0,7)]] #CLRS pp.595
    print 'Adj: Adj[u] stores (v,w[u,v])'
    pprint(Adj)
    pi, d = dijkstra(Adj, 0)
    print 'Pi:', pi
    print 'd :', d
